Home | | Latest | About | Random
# Week 4 Monday
Dear Class,
Today we work on some typical programming patterns:
- Solving **user-input problems**, in particular when we cannot anticipate when the program will end. A solution to this is to use a loop, and the various user input functions we've seen before. This is section 8.4.
- Using an **intermediate variables** that hold current calculated values.
On Wednesday we will start section 9 on functions, but section 9 will not be on midterm 1.
**HW3** is due this Friday at 10pm, its material is also part of midterm 1 so it is best to do it.
**PS.** Something **experimental** I've been twiddling with is an "online C++ compiler" [https://jupy.bonsoon.net/](https://jupy.bonsoon.net/) in case you *really* have trouble with your IDE. This solution isn't perfect as well:
- It saves everything in the browser, so if you clear cache, everything goes poof. So you have to save it often. It does have folders to help you organize code, and runs the current code only.
- How it takes user input is "somewhat" different, as it will always request input on a new separate line. This would look different from your usual console experience.
- It's not like your IDE, and cannot highlight errors as you type.
- It can be slow to start up sometimes, a bit janky.
But you can try this as a last resort if desperate. But the point is if it can get you to try writing code faster and experiment more often, the better, regardless of the solution is. Nevertheless, you should still go back to your IDE to double check work, and check if Gradescope takes your work if it is to be graded.
-- B.
.
.
.
.
## A sum program.
Let us write a program that does the following:
- Prompt the user for a list of `int`s separated by a space ` ` in between.
- Upon hitting `ENTER`, the program computes the sum of these `int`s
- And when it is finished, ask the user if they want to continue and repeat this program again, by asking a `y` or `n` response.
- If `y`, then we continue.
- If `n` we exit the program completely.
So we envision a program that would look like this:
```cmd
Enter a list of ints separated by a space in between:
4
Their sum is 4
Shall we do it again? (y / n)
y
Enter a list of ints separated by a space in between:
5 1 2 5
Their sum is 13
Shall we do it again? (y / n)
y
Enter a list of ints separated by a space in between:
0 -3 3 100
Their sum is 100
Shall we do it again? (y / n)
n
Good bye!
```
,
,
,
,
,
## Shall we do it again?
We can solve this by a common pattern:
- Be in a `while` loop that is always `true`.
- Ask for `y / n`.
- If user enters `n` we break out of the loop.
(Let us assume the user will always follow the instruction.)
```cpp
#include
using namespace std;
int main() {
char response;
while (true) {
cout << "Shall we do it again? (y / n)" << endl;
cin >> response; // taking input
if (response == 'n') {
cout << "Good bye!";
break;
}
}
}
```
- Use your knowledge of the input buffer and `cin` to trace out what happens as the user types in `y`, `ENTER`, `y`, `ENTER`, `n`.
- If instead we replace the line marked by the comment `// taking input` by `response = cin.get();`, what will happen?
- What if we replace it by `response = cin.get(); cin.ignore();`?
- Turns out this is not very robust. What would happen if a user is to enter `yn` followed by `ENTER`?
- What about `yyn`, or `yyyn`?
.
.
.
.
.
## Taking inputs separated by a space.
Often a program would ask for a list of inputs. We can enter it by separating the values by a space. But how should the program parse it, if we do not know how long the list would be?
An example program could be counting how many numbers we inputted, separated by spaces. Like so:
```cmd
Enter a list of ints separated by space in between:
5 1 2 5 6 9
You entered 6 numbers.
```
A suggestion is to use a `while` loop with `cin`. And introduce an intermediate variable call `count` to keep the current count. Also, to determine when to exit the loop, we can use `cin.peek()` to see if the next character is a `\n`, that indicated the end of this data input. In this case, we sometimes call `\n` a **sentinel value**, something that indicates and signals we should do something.
```cpp
#include
using namespace std;
int main() {
int number;
int count = 0;
cout << "Enter a list of ints separated by space in betewen:" << endl;
while (true) {
cin >> number;
count++;
if (cin.peek() == '\n') {
break;
}
}
cout << "You entered " << count << " numbers.";
return 0;
}
```
- Examine what would happen if we enter `1 2 3 4`?
- How about ` 1 2 3 4`?
- How about `1 2 3 4 `?
To deal with trailing spaces, we can again use a `while` loop to manage them, by inserting this somewhere appropriate:
```cpp
while (cin.peek() == ' ') { cin.ignore(); }
```
- Try to find out where to make the input `1 2 3 4 ` work as "intended".
**Remark.** It is always a headache when user do not enter things as specified. Nevertheless, these examples serve as good illustration the behavior of the input buffer the various `cin` member functions.
**Now, put these ideas together to form the program that sum a list of `int`s separated by spaces!**
.
.
.
.
.
## How to swap two numbers?
Let us say there are two `int` variables call `a,b`, how would one swap their values?
Here's a common pattern: Use an **intermediate variable**! Here we use `int x` to hold a place to swap the values in `a` and `b`.
```cpp
#include
using namespace std;
int main() {
int a, b, x;
cout << "Enter two ints, separated by space:" << endl;
cin >> a >> b;
cout << "a is " << a << " and b is " << b << endl;
x = b; // stores value of b into variable x
b = a; // now overwrites b with value of a
a = x; // now overwrites a with value of x, what b was initially
cout << "after swapping:" << endl;
cout << "a is " << a << " and b is " << b << endl;
}
```
.
.
.
.
.
## Binary numbers.
We've been talking about numbers in "bits" casually, numbers in zeros and ones. These are binary numbers. Let us learn how to write a number in binary.
List the powers of 2 in increasing order from *right* to _left_, like this:
```
... 2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0
... 128 64 32 16 8 4 2 1
```
- Now take your (positive) integer `N` and find the largest power of 2 that fits in `N`.
- Put a `1` above that power of 2, and **subtract** from `N` that power of 2.
- Now go down the next power of 2:
- If this next power of 2 fits, write a `1` above, and subtract this power of 2.
- If not, write a `0` above.
- Repeat to the next smaller power of 2, until no more non-negative power of 2s.
So say your number `N = 50`.
- The largest power of 2 that fits in `50` is is `2^5`.
- Write a `1` above `2^5`. Now `50-2^5 = 18`.
- The next power of 2 `2^4` fits in `18`.
- Write a `1` above `2^4`, subtract we get `2`.
- The next power of 2 `2^3` does not fit in `2`.
- Write a `0`.
- The next power of 2 `2^2` does not fit in `2`.
- Write a `0`
- The next power of 2 `2^1` fits in `2`.
- Write a `1` and subtract, we get `0` left.
- The next power of 2 `2^0` does not fit in `0`.
- Write a `0`. We have no more powers of 2.
So the binary representation of `50` is `110010`. In another word, we have $$
50 = 1\cdot 2^{5} + 1\cdot 2^{4} + 0\cdot 2^{2}+ 0\cdot 2^{3} + 1\cdot 2^{1} + 0\cdot 2^{0}
$$
You can do this with other bases as well, but instead, you will ask how many _copies_ of the power will fit. For example in base-3, we can either fit `0,1,` or `2` copies of some power of 3 each time, that will give you the corresponding ternary "digit"!
.
.
.
.
.
---
Good to try these on your own -- see if you can take a description, and turn it into code!
## Sieve of Eratosthenes.
[Eratosthenes](https://en.wikipedia.org/wiki/Eratosthenes) lived around 276 BC to 195 BC, and he was one smart cookie. Among his great achievements ([[1-teaching/summer program 2023/week 1/Cosmic_distance_ladder|estimating the radius of Earth]], the axial tilt of Earth, dating the events of the Trojan war at around 1000 BC, being the chief librarian of the Library of Alexandria...) he came up with an efficient way to find **prime numbers** (positive integers with exactly two divisors) called **the sieve of Eratosthenes**. It goes like this:
- Say you want to find all prime numbers $\le N$. Write down the numbers 1, 2, 3, ...., N.
- Cross 1 out, as 1 is not a prime.
- Now, for the next number that is not crossed out, say $p$, box it, it is a **prime**. Then cross out every multiple of this number you just circled (except $p$ itself), starting at $p^{2}$. That is, cross out $p^{2},(p+1)p,(p+2)p,...$ and so on, up to your chosen $N$.
- Repeat to the next number that is not yet crossed out.
For example, if $N = 10$, it goes like this.
- Cross out 1.
- Box 2, a prime. Cross out 4, 6, 8, 10.
- Box 3, a prime. Cross out 9.
- Box 5, a prime. Cross out 10.
- Box 7, a prime.
- We left with this $\cancel1, \fbox{2}, \fbox{3}, \cancel4, \fbox{5}, \cancel6, \fbox{7}, \cancel8, \cancel9, \cancel{10}$
Cool! We have four prime numbers less than equal to 10. Hmm...
- How many prime numbers are there less than equal to 100?
- How about less equal to 1000? or 1000000?
Let's write some C++ to find out!
(Though there are faster ways to list primes, the sieve is one of the top shelf methods!)
- To keep track of which number is a prime or not, we can create a giant string of length `N+1` characters, say all `t`'s. And we use its position `i` to keep track whether the integer `i` is a prime or not. If `i` is a prime, keep index `i` character as `t`, otherwise make it `f`.
- Later, we will see another data type that is suitable to store a *list* of things by using the `vector` class!
- Use an intermediate variable to keep track of counting how many primes.
[[1-teaching/ucla-2026-fall-pic-10a/sieve-answer|suggested answer to Eratosthenes sieve]]
Some more cool examples you can do with loops.
## A magic carpet.
Here we draw something according to the following rules.
- Start with a two character string `* `, and print it out on its own line.
- For the next row we do the following:
- Set the index-0 character of the next row to be `*`
- For each nonzero index-`i` character of the next row, check the index-`i` and index-`(i-1)` character of the previous row:
- If those two characters are different, then index-`i` of next row is `*`.
- If they are the same, then index-`i` of next row is ` `.
- Concatenate a space ` ` to this next row, so that it has length 1 longer than the previous row.
- Print out this new line.
- Repeat above for however many times you like.
Hint: Use two `string` variables to keep track of `current_row` and `next_row`.
Try coding that up! Try describing what you see!
[[1-teaching/ucla-2026-fall-pic-10a/sierpinski-answer|suggested code answer]]